和正式题目略有不同，可忽略不计
AT_AGC_A - MIN CUT OF GRAPH OF MIN WEIGHT
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
SCORE: 900 POINTS
PROBLEMS STATEMENT
There is a weighted tree T\bm{T}T with N\bm{N}N vertices numbered 1 to N\bm{N}N.The i-th edge of T connects vertices AiA_iAi and BiB_iBi with weight CiC_iCi .
We now construct a complete indirected gragh C\bm{C}C with N\bm{N}N vertices numbered 1 to N\bm{N}N, based on T\bm{T}T. For each edge of G\bm{G}G, the capacity is defined as follows.
THE CAPACITY OF EDGE
(i,j) of G\bm{G}G is the minimum weight of an edge contained in the path connecting vertices i and j on T\bm{T}T.
Let f(i,j) be the capacity of the minimumcut separating vertices i and j on G\bm{G}G.
FIND ∑(1≤I<J≤N)∑_(1≤I<J≤N)∑( 1≤I<J≤N)·F\BM{F}F(I,J) , MODULO 998244353.
SOLVE S\BM{S}S CASES FOR EACH INPUT.
CONSTRAINTS
1. 1 ≤ S\bm{S}S ≤ 125000
2. 2 ≤ N\bm{N}N ≤ 250000
3. 1 ≤ AiA_iAi ,BiB_iBi ≤N
4. 1 ≤ CiC_ iCi ≤ 101210^{12}1012
5. The input graph is a tree.
6. The sum of N\bm{N}N over the S\bm{S}S cases is at most 250000.
7. All input values are integers.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
INPUT
THE INPUT IS GIVEN FROM STANDARD INPUT IN THE FOLLOWING FORMAT:
Scase 1case 2⋮case SS \\ \text{case } 1 \\ \text{case } 2 \\ \vdots \\ \text{case } S Scase 1case 2⋮case S
EACH TEST CASE IS GIVEN IN THE FOLLOWING FORMAT:
NA1 B1 C1A2 B2 C2⋮AN−1 BN−1 CN−1N \\ A_1 \ B_1 \ C_1 \\ A_2 \ B_2 \ C_2 \\ \vdots \\ A_{N-1} \ B_{N-1} \ C_{N-1} NA1 B1 C1 A2 B2 C2 ⋮AN−1 BN−1 CN−1
OUTPUT
FOR EACH TEST CASE, OUTPUT THE ANSWER.
SAMPLE INPUT 1
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
SAMPLE OUTPUT 1
EXPLANATION
In the first test case, the capacities of edges (1,2)$, (1,3)(1,3)(1,3), and $(2,3) of G\bm{G}G are 111, 111, and 101010, respectively. The answer is:
f(1,2)+f(1,3)+f(2,3)=2+2+11=15f(1,2) + f(1,3) + f(2,3) = 2 + 2 + 11 = 15f(1,2)+f(1,3)+f(2,3)=2+2+11=15
